package exercises.newcoder.solution;

import java.util.Scanner;

/**
 * <a href="https://www.nowcoder.com/study/live/716/1/9?autoplay=1">
 * 第9节 随堂习题-二分查找某数</a>
 *
 * <p><span color="#87CEEB">描述:</span>
 * 给你一个n代表有一个长度为n的有序数组，然后给你一个k，你需要判断这个k是否在数组里面，
 * 如果存在就返回这个数第一次出现位置的下标，如果不存在输出-1
 * <p>
 * 输入描述:
 * <p>
 * 第一行输入一个n，k，其中n代表有n个数字，k代表你需要查找的元素
 * 第二行输入n个数
 * <p>
 * 输出描述:
 * <p>
 * 如果在数组里面找到了k，输出k所在的下标，如果k不在，就输出-1
 *
 * @author or2
 * @date 2021年09月27日 时间: 20:38
 */
public class Introductory9 {
    public static void main(String[] args) {
        /*处理输入*/
        Scanner scanner = new Scanner(System.in);
        int amount = scanner.nextInt();
        int target = scanner.nextInt();
        int[] arr = new int[amount];
        for (int i = 0; i < arr.length; i++)
            arr[i] = scanner.nextInt();
        /*初始化辅助*/
        int left = 0, right = amount;
        int midIndex;
        /*二分查找 [left, right)*/
        while (left < right) {
            /*比较大小*/
            midIndex = left + (right - left >> 1);
            int sub = arr[midIndex] - target;
            /*找到目标*/
            if (sub == 0) {
                while (arr[--midIndex] == target) ;
                System.out.println(midIndex + 1);
                return;
            /*向后继续搜索*/
            } else if (sub < 0)
                left = midIndex + 1;
            else
                right = midIndex;
        }

        /*没有找到*/
        System.out.println(-1);
    }
}
